The present invention relates generally to computer system hardware design. More particularly, it relates to a system and method for using valid bits to identify available space in an overflow buffer.
In the field of computer architecture, data received by a processor or controller may be stored in a cache array while it is processed. Data may be received by the controller on one or more data input signals in a more-or-less steady stream, in regular intervals. It may then be stored in a cache array until it can be processed. When the controller is done processing the data, it may be removed from the cache array, and its cache memory space becomes available for a new data element.
A problem occurs when the controller receives data faster than it processes the data. The cache array may become full or otherwise inaccessible temporarily, causing it to be unable to store additional incoming data temporarily. One method for handling this situation uses an overflow data buffer, or queue. When the cache array is full or inaccessible, incoming data is stored in the overflow buffer until the cache array becomes available. It is then removed from the overflow buffer and stored in the cache array.
In one embodiment, the overflow buffer may contain a plurality of data entries that can be accessed in any order. When the buffer is accessed randomly, it is desirable to have an efficient means of determining whether each entry has data stored to it. If an entry already has data stored, then the controller may not want to write a new entry over the existing data and instead may want to use an open entry, if one is available. Each data entry in the buffer may contain a valid bit that indicates whether the entry currently stores data. In one example, the valid bit may be set when data is stored to the buffer, and may be reset when data is removed from the buffer.
A further problem occurs when the cache array cannot be accessed immediately and the overflow buffer becomes full or otherwise inaccessible. The controller may be receiving data at a regular rate, and will need a location to store this incoming data, if the cache array is full or otherwise inaccessible. If the overflow buffer is also inaccessible, then it may be desirable to suspend the flow of incoming data until space becomes available. This is one purpose of the valid bit. Existing methods and systems check the valid bits to determine whether there are any empty entries in the buffer. Checking for open entries is difficult when the controller has more than one data input. For example, a particular controller may have two lines of incoming data and may use an overflow buffer having 24 entries. Before accepting data from the two inputs, the controller must determine whether there are at least two open entries in the over flow buffer.
Existing methods of checking the buffer require too much time. One such method uses a ripple adder to check the valid bits of each of the overflow entries. If it detects two or more open entries, then the controller receives the input. This method requires substantial time for the buffer check signal to ripple through logic gates for each of the 24 entries. The problem is exacerbated for buffers having more entries. The incoming data may be received at a faster rate than the time required by the ripple adder, in which case, these methods limit processing speed. For example, the inputs may receive data on every clock cycle, yet existing methods require more than one clock cycle to determine whether the buffer has sufficient space to receive the incoming data. As a result, existing systems limit the speed at which data can be received, or fail to indicate the current state of the buffer on the current clock cycle on which the buffer is queried. Systems that fail to determine buffer availability on the current clock cycle may require additional hardware to compensate for change in clock cycle.
What is needed is a method and system for more quickly determining whether an overflow buffer has room enough to receive additional data entries. In particular, what is needed is a method and system for determining whether or not a specified number of entries, or saturated count, are available in an overflow buffer having multiple entries.
A computer hardware system is disclosed for determining whether a data buffer having a plurality of entries can accept additional data. The system has multiple stages, having one or more adders/encoders that process the data buffer entries"" valid bits in parallel. Entries are organized into groups and each group is associated with a first-stage adder/encoder. Valid bits and their complements for groups of entries are received into multiple first-stage adders that compute and output encoded values indicating the number of available entries within each group. Each adder calculates a partial sum of the total number of available entries in the buffer, which sum is referred to as a first-stage total. Each first-stage total represents the total number of available entries for the particular group or a saturated count if the total equals or exceeds a specified number of entries. Each first-stage adder/encoder then encodes its first-stage total for ease of processing. In one embodiment, in which the saturated count is two, the system determines whether two entries are available in the buffer, so the encoders indicate whether the first-stage total shows zero, one, or more than one available entry (that is, the saturated count).
The first-stage totals are then sent to a second stage having adders/encoders that are substantially the same as the first-stage adders/encoders. The second-stage adders receive the two-bit encoded first-stage totals and calculate a second-stage total that represents the number of available entries in the data buffer that are input into the second-stage adder. If the implementation has multiple second-stage adders/encoders, then the second-stage totals may be output to a third-stage adder/encoder that makes a final determination of whether the buffer has available room. Other implementations use additional stages.
In one embodiment, the buffer has twenty-four entries and the system is implemented to determine whether two or more of these entries are available. The number of available entries for which the system is searching is referred to as the saturated count. In one embodiment, the system determines whether or not the saturated count is reached and does not indicate the particular number of available entries above the saturated count. In the embodiment shown, six first-stage adders/encoders each receive four valid bits and their complements. Two second-stage adders/encoders each receive two-bit inputs from three first-stage adders, and a single third-stage adder receives two-bit inputs from the two second-stage adders. In one embodiment, the system analyzes the buffer during a single clock cycle so that the output of the final-stage adder reflects the current availability of the buffer. In one embodiment, the system uses a coding scheme that correlates a saturated count with a pre-charged state of the adder, such that the output of the adder does not transition from its pre-charged state when it receives a saturated count.
A method is also disclosed for analyzing a data buffer to determine whether a data buffer having a plurality of entries can accept additional entries. Groups of valid bits and their complements are analyzed in parallel by multiple first-stage adders to determine the number of available buffer entries in the group considered, or first-stage total. The first-stage total is encoded in a two-bit code and sent to a second-stage adder that sums the first-stage totals from two or more first-stage adders and outputs an encoded second-stage total representing the sum of the first-stage totals considered by the second-stage adder. The second-stage totals are sent to a third-stage adder that receives all of the second-stage totals and outputs an indicator showing whether the buffer has available space.